package com.yanceysong.codetop.s1_s10;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName S6_Mid_15_三数之和
 * @Description
 * @date 2025/8/17 22:02
 * @Author yanceysong
 * @Version 1.0
 */
public class S6_Mid_15_三数之和 {
    /**
     * LeetCode：
     * <a href="https://leetcode.cn/problems/3sum/description/">...</a>
     * 给你一个整数数组 nums ，判断是否存在三元组
     * [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k
     * 同时还满足 nums[i] + nums[j] + nums[k] == 0
     * 请你返回所有和为 0 且不重复的三元组。
     * <p>
     * 注意：答案中不可以包含重复的三元组。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [-1,0,1,2,-1,-4]
     * 输出：[[-1,-1,2],[-1,0,1]]
     * 解释：
     * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
     * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
     * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
     * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
     * 注意，输出的顺序和三元组的顺序并不重要。
     * 示例 2：
     * <p>
     * 输入：nums = [0,1,1]
     * 输出：[]
     * 解释：唯一可能的三元组和不为 0 。
     * 示例 3：
     * <p>
     * 输入：nums = [0,0,0]
     * 输出：[[0,0,0]]
     * 解释：唯一可能的三元组和为 0 。
     * <p>
     * 提示：
     * <p>
     * 3 <= nums.length <= 3000
     * -105 <= nums[i] <= 105
     * <p>
     * ==================== 三数之和算法图解 ====================
     * <p>
     * 算法思路：排序 + 双指针 + 去重
     * 1. 排序数组，便于去重和双指针操作
     * 2. 外层循环固定第一个数
     * 3. 内层使用双指针寻找另外两个数
     * 4. 根据三数之和调整指针位置
     * 5. 跳过重复元素避免重复三元组
     * <p>
     * 执行示例：nums = [-1,0,1,2,-1,-4]
     * <p>
     * 第一步：排序数组
     * 原数组: [-1, 0, 1, 2, -1, -4]
     * 排序后: [-4, -1, -1, 0, 1, 2]
     * .        ↑   ↑   ↑  ↑  ↑  ↑
     * .        0   1   2  3  4  5  (索引)
     * <p>
     * 第二步：外层循环固定第一个数
     * <p>
     * 第1轮：firstIndex=0, firstNum=-4
     * 数组: [-4, -1, -1, 0, 1, 2]
     * .     ↑   ↑              ↑
     * .    first left          right
     * <p>
     * 目标：找到 leftNum + rightNum = -firstNum = 4
     * <p>
     * 双指针过程：
     * left=1, right=5: -1 + 2 = 1 < 4, left++
     * left=2, right=5: -1 + 2 = 1 < 4, left++
     * left=3, right=5: 0 + 2 = 2 < 4, left++
     * left=4, right=5: 1 + 2 = 3 < 4, left++
     * left=5, right=5: left >= right, 结束
     * 结果：无解
     * <p>
     * 第2轮：firstIndex=1, firstNum=-1
     * 数组: [-4, -1, -1, 0, 1, 2]
     * .      ↑   ↑           ↑
     * .    first left      right
     * <p>
     * 目标：找到 leftNum + rightNum = -firstNum = 1
     * <p>
     * 双指针过程：
     * left=2, right=5: -1 + 2 = 1 = 1 ✓ 找到解！
     * 添加三元组：[-1, -1, 2]
     * <p>
     * 去重处理：
     * left=2, nums[2]=-1, nums[3]=0, 不相等，left++
     * right=5, nums[5]=2, nums[4]=1, 不相等，right--
     * 继续：left=3, right=4: 0 + 1 = 1 = 1 ✓ 找到解！
     * 添加三元组：[-1, 0, 1]
     * <p>
     * 第3轮：firstIndex=2, firstNum=-1
     * 跳过重复：nums[2] == nums[1]，continue
     * <p>
     * 第4轮：firstIndex=3, firstNum=0
     * 数组: [-4, -1, -1, 0, 1, 2]
     * .      ↑  ↑   ↑
     * .    first left right
     * <p>
     * 目标：找到 leftNum + rightNum = 0
     * left=4, right=5: 1 + 2 = 3 > 0, right--
     * left=4, right=4: left >= right, 结束
     * 结果：无解
     * <p>
     * 第5轮：firstIndex=4, firstNum=1 > 0
     * 优化剪枝：第一个数大于0，后面都是正数，不可能和为0，break
     * <p>
     * 最终结果：[[-1, -1, 2], [-1, 0, 1]]
     * <p>
     * 关键优化点：
     * 1. 排序后剪枝：firstNum > 0 时直接break
     * 2. 第一个数去重：跳过重复的firstNum
     * 3. 双指针去重：找到解后跳过重复的leftNum和rightNum
     * 4. 双指针移动：根据sum与0的关系决定移动方向
     * <p>
     * 去重机制图解：
     * <p>
     * 第一层去重（外层循环）：
     * [-4, -1, -1, 0, 1, 2]
     * ↑   ↑
     * 处理  跳过（重复）
     * <p>
     * 第二层去重（找到解后）：
     * 找到解：[-1, -1, 2]
     * left指针：跳过重复的-1
     * right指针：跳过重复的2（如果有）
     * <p>
     * 时间复杂度：O(n²) - 外层循环O(n)，内层双指针O(n)
     * 空间复杂度：O(logn) - 排序的递归栈空间
     * <p>
     * ================================================================
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        int arrayLength = nums.length;

        // 边界检查：少于3个元素无法组成三元组
        if (arrayLength < 3) {
            return resultList;
        }

        // 排序数组，为双指针和去重做准备
        Arrays.sort(nums);

        // 外层循环：枚举第一个数
        for (int firstIndex = 0; firstIndex < arrayLength; firstIndex++) {
            int firstNum = nums[firstIndex];

            // 优化剪枝：如果第一个数大于0，后面都是正数，三数之和必然大于0
            if (firstNum > 0) {
                break;
            }

            // 去重：跳过与前一个相同的第一个数
            if (firstIndex > 0 && firstNum == nums[firstIndex - 1]) {
                continue;
            }

            // 双指针：在剩余数组中寻找另外两个数
            int leftIndex = firstIndex + 1;        // 左指针：从第一个数的下一位开始
            int rightIndex = arrayLength - 1;      // 右指针：从数组末尾开始

            while (leftIndex < rightIndex) {
                int leftNum = nums[leftIndex];
                int rightNum = nums[rightIndex];
                int threeSum = firstNum + leftNum + rightNum;

                if (threeSum == 0) {
                    // 找到一个满足条件的三元组
                    resultList.add(Arrays.asList(firstNum, leftNum, rightNum));

                    // 去重：跳过左指针的重复元素
                    while (leftIndex < rightIndex && nums[leftIndex] == nums[leftIndex + 1]) {
                        leftIndex++;
                    }

                    // 去重：跳过右指针的重复元素
                    while (leftIndex < rightIndex && nums[rightIndex] == nums[rightIndex - 1]) {
                        rightIndex--;
                    }

                    // 移动双指针继续寻找下一个可能的组合
                    leftIndex++;
                    rightIndex--;

                } else if (threeSum < 0) {
                    // 三数之和小于0，需要增大和值，左指针右移
                    leftIndex++;
                } else {
                    // 三数之和大于0，需要减小和值，右指针左移
                    rightIndex--;
                }
            }
        }

        return resultList;
    }

    public static void main(String[] args) {
        S6_Mid_15_三数之和 solution = new S6_Mid_15_三数之和();

        System.out.println("=== 三数之和测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 重复元素测试
        System.out.println("\n--- 测试3: 重复元素测试 ---");
        testDuplicateElements(solution);

        // 测试4: 特殊数值测试
        System.out.println("\n--- 测试4: 特殊数值测试 ---");
        testSpecialValues(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 辅助方法：打印二维列表
     */
    private static void printResult(List<List<Integer>> result) {
        if (result.isEmpty()) {
            System.out.print("[]");
            return;
        }

        System.out.print("[");
        for (int i = 0; i < result.size(); i++) {
            List<Integer> triplet = result.get(i);
            System.out.print("[");
            for (int j = 0; j < triplet.size(); j++) {
                System.out.print(triplet.get(j));
                if (j < triplet.size() - 1) {
                    System.out.print(",");
                }
            }
            System.out.print("]");
            if (i < result.size() - 1) {
                System.out.print(",");
            }
        }
        System.out.print("]");
    }

    /**
     * 辅助方法：验证结果是否包含期望的三元组
     */
    private static boolean containsTriplet(List<List<Integer>> result, int[] triplet) {
        for (List<Integer> list : result) {
            if (list.size() == 3 &&
                list.get(0) == triplet[0] &&
                list.get(1) == triplet[1] &&
                list.get(2) == triplet[2]) {
                return true;
            }
        }
        return false;
    }

    /**
     * 辅助方法：验证所有三元组的和是否为0
     */
    private static boolean validateAllSumsZero(List<List<Integer>> result) {
        for (List<Integer> triplet : result) {
            if (triplet.size() != 3) return false;
            int sum = triplet.get(0) + triplet.get(1) + triplet.get(2);
            if (sum != 0) return false;
        }
        return true;
    }

    /**
     * 辅助方法：验证结果中没有重复的三元组
     */
    private static boolean validateNoDuplicates(List<List<Integer>> result) {
        for (int i = 0; i < result.size(); i++) {
            for (int j = i + 1; j < result.size(); j++) {
                List<Integer> triplet1 = result.get(i);
                List<Integer> triplet2 = result.get(j);
                if (triplet1.equals(triplet2)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S6_Mid_15_三数之和 solution) {
        // 示例1: [-1,0,1,2,-1,-4] -> [[-1,-1,2],[-1,0,1]]
        int[] nums1 = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result1 = solution.threeSum(nums1);

        System.out.print("输入: " + Arrays.toString(nums1) + " -> 输出: ");
        printResult(result1);
        System.out.println();

        // 验证结果
        assert validateAllSumsZero(result1) : "示例1：所有三元组的和应该为0";
        assert validateNoDuplicates(result1) : "示例1：不应该有重复的三元组";
        assert containsTriplet(result1, new int[]{-1, -1, 2}) : "示例1：应该包含[-1,-1,2]";
        assert containsTriplet(result1, new int[]{-1, 0, 1}) : "示例1：应该包含[-1,0,1]";
        assert result1.size() == 2 : "示例1：应该有2个三元组";

        // 示例2: [0,1,1] -> []
        int[] nums2 = {0, 1, 1};
        List<List<Integer>> result2 = solution.threeSum(nums2);

        System.out.print("输入: " + Arrays.toString(nums2) + " -> 输出: ");
        printResult(result2);
        System.out.println(" (期望: [])");

        assert result2.isEmpty() : "示例2：应该返回空列表";

        // 示例3: [0,0,0] -> [[0,0,0]]
        int[] nums3 = {0, 0, 0};
        List<List<Integer>> result3 = solution.threeSum(nums3);

        System.out.print("输入: " + Arrays.toString(nums3) + " -> 输出: ");
        printResult(result3);
        System.out.println(" (期望: [[0,0,0]])");

        assert validateAllSumsZero(result3) : "示例3：所有三元组的和应该为0";
        assert result3.size() == 1 : "示例3：应该有1个三元组";
        assert containsTriplet(result3, new int[]{0, 0, 0}) : "示例3：应该包含[0,0,0]";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S6_Mid_15_三数之和 solution) {
        // 测试1: 最小长度数组 [1,2,3]
        int[] nums1 = {1, 2, 3};
        List<List<Integer>> result1 = solution.threeSum(nums1);

        System.out.print("最小长度无解: " + Arrays.toString(nums1) + " -> 输出: ");
        printResult(result1);
        System.out.println(" (期望: [])");

        assert result1.isEmpty() : "最小长度无解测试失败";

        // 测试2: 最小长度有解 [-1,0,1]
        int[] nums2 = {-1, 0, 1};
        List<List<Integer>> result2 = solution.threeSum(nums2);

        System.out.print("最小长度有解: " + Arrays.toString(nums2) + " -> 输出: ");
        printResult(result2);
        System.out.println(" (期望: [[-1,0,1]])");

        assert validateAllSumsZero(result2) : "最小长度有解：和应该为0";
        assert result2.size() == 1 : "最小长度有解：应该有1个三元组";
        assert containsTriplet(result2, new int[]{-1, 0, 1}) : "最小长度有解：应该包含[-1,0,1]";

        // 测试3: 全正数 [1,2,3,4,5]
        int[] nums3 = {1, 2, 3, 4, 5};
        List<List<Integer>> result3 = solution.threeSum(nums3);

        System.out.print("全正数: " + Arrays.toString(nums3) + " -> 输出: ");
        printResult(result3);
        System.out.println(" (期望: [])");

        assert result3.isEmpty() : "全正数测试失败";

        // 测试4: 全负数 [-5,-4,-3,-2,-1]
        int[] nums4 = {-5, -4, -3, -2, -1};
        List<List<Integer>> result4 = solution.threeSum(nums4);

        System.out.print("全负数: " + Arrays.toString(nums4) + " -> 输出: ");
        printResult(result4);
        System.out.println(" (期望: [])");

        assert result4.isEmpty() : "全负数测试失败";

        // 测试5: 只有一个0 [0,1,2]
        int[] nums5 = {0, 1, 2};
        List<List<Integer>> result5 = solution.threeSum(nums5);

        System.out.print("只有一个0: " + Arrays.toString(nums5) + " -> 输出: ");
        printResult(result5);
        System.out.println(" (期望: [])");

        assert result5.isEmpty() : "只有一个0测试失败";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试重复元素
     */
    private static void testDuplicateElements(S6_Mid_15_三数之和 solution) {
        // 测试1: 多个重复元素 [-2,0,0,2,2]
        int[] nums1 = {-2, 0, 0, 2, 2};
        List<List<Integer>> result1 = solution.threeSum(nums1);

        System.out.print("多个重复元素: " + Arrays.toString(nums1) + " -> 输出: ");
        printResult(result1);
        System.out.println();

        assert validateAllSumsZero(result1) : "多个重复元素：和应该为0";
        assert validateNoDuplicates(result1) : "多个重复元素：不应该有重复三元组";
        assert containsTriplet(result1, new int[]{-2, 0, 2}) : "多个重复元素：应该包含[-2,0,2]";

        // 测试2: 大量重复 [-1,-1,-1,0,1,1,1]
        int[] nums2 = {-1, -1, -1, 0, 1, 1, 1};
        List<List<Integer>> result2 = solution.threeSum(nums2);

        System.out.print("大量重复: " + Arrays.toString(nums2) + " -> 输出: ");
        printResult(result2);
        System.out.println();

        assert validateAllSumsZero(result2) : "大量重复：和应该为0";
        assert validateNoDuplicates(result2) : "大量重复：不应该有重复三元组";
        assert containsTriplet(result2, new int[]{-1, 0, 1}) : "大量重复：应该包含[-1,0,1]";

        // 测试3: 四个0 [0,0,0,0]
        int[] nums3 = {0, 0, 0, 0};
        List<List<Integer>> result3 = solution.threeSum(nums3);

        System.out.print("四个0: " + Arrays.toString(nums3) + " -> 输出: ");
        printResult(result3);
        System.out.println(" (期望: [[0,0,0]])");

        assert validateAllSumsZero(result3) : "四个0：和应该为0";
        assert result3.size() == 1 : "四个0：应该只有1个三元组";
        assert containsTriplet(result3, new int[]{0, 0, 0}) : "四个0：应该包含[0,0,0]";

        // 测试4: 复杂重复模式 [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
        int[] nums4 = {-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6};
        List<List<Integer>> result4 = solution.threeSum(nums4);

        System.out.print("复杂重复模式: " + Arrays.toString(nums4) + " -> 输出: ");
        printResult(result4);
        System.out.println();

        assert validateAllSumsZero(result4) : "复杂重复模式：和应该为0";
        assert validateNoDuplicates(result4) : "复杂重复模式：不应该有重复三元组";

        System.out.println("✓ 重复元素测试通过");
    }

    /**
     * 测试特殊数值
     */
    private static void testSpecialValues(S6_Mid_15_三数之和 solution) {
        // 测试1: 包含最大最小值 [-100000, 0, 100000]
        int[] nums1 = {-100000, 0, 100000};
        List<List<Integer>> result1 = solution.threeSum(nums1);

        System.out.print("极值测试: " + Arrays.toString(nums1) + " -> 输出: ");
        printResult(result1);
        System.out.println(" (期望: [[-100000,0,100000]])");

        assert validateAllSumsZero(result1) : "极值测试：和应该为0";
        assert result1.size() == 1 : "极值测试：应该有1个三元组";
        assert containsTriplet(result1, new int[]{-100000, 0, 100000}) : "极值测试：应该包含[-100000,0,100000]";

        // 测试2: 大数值组合 [-50000, 25000, 25000]
        int[] nums2 = {-50000, 25000, 25000};
        List<List<Integer>> result2 = solution.threeSum(nums2);

        System.out.print("大数值组合: " + Arrays.toString(nums2) + " -> 输出: ");
        printResult(result2);
        System.out.println(" (期望: [[-50000,25000,25000]])");

        assert validateAllSumsZero(result2) : "大数值组合：和应该为0";
        assert result2.size() == 1 : "大数值组合：应该有1个三元组";

        // 测试3: 混合正负大数 [-99999, -1, 100000]
        int[] nums3 = {-99999, -1, 100000};
        List<List<Integer>> result3 = solution.threeSum(nums3);

        System.out.print("混合正负大数: " + Arrays.toString(nums3) + " -> 输出: ");
        printResult(result3);
        System.out.println(" (期望: [[-99999,-1,100000]])");

        assert validateAllSumsZero(result3) : "混合正负大数：和应该为0";
        assert result3.size() == 1 : "混合正负大数：应该有1个三元组";

        // 测试4: 接近溢出的情况 [-100000, -100000, 200000] (但不会溢出)
        int[] nums4 = {-100000, -100000, 200000};
        List<List<Integer>> result4 = solution.threeSum(nums4);

        System.out.print("接近溢出: " + Arrays.toString(nums4) + " -> 输出: ");
        printResult(result4);
        System.out.println();

        assert validateAllSumsZero(result4) : "接近溢出：和应该为0";

        // 测试5: 复杂的大数组合
        int[] nums5 = {-10000, -5000, -1000, 0, 1000, 5000, 10000, 15000};
        List<List<Integer>> result5 = solution.threeSum(nums5);

        System.out.print("复杂大数组合: " + Arrays.toString(nums5) + " -> 输出: ");
        printResult(result5);
        System.out.println();

        assert validateAllSumsZero(result5) : "复杂大数组合：和应该为0";
        assert validateNoDuplicates(result5) : "复杂大数组合：不应该有重复三元组";

        System.out.println("✓ 特殊数值测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S6_Mid_15_三数之和 solution) {
        // 测试1: 中等规模数组 (100个元素)
        System.out.println("性能测试1: 100个元素");
        testPerformanceCase(solution, 100);

        // 测试2: 较大规模数组 (500个元素)
        System.out.println("性能测试2: 500个元素");
        testPerformanceCase(solution, 500);

        // 测试3: 大规模数组 (1000个元素)
        System.out.println("性能测试3: 1000个元素");
        testPerformanceCase(solution, 1000);

        // 测试4: 最坏情况 - 大量重复元素
        System.out.println("性能测试4: 最坏情况 - 大量重复");
        testWorstCasePerformance(solution);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S6_Mid_15_三数之和 solution, int size) {
        // 生成测试数据：包含正数、负数、零
        int[] nums = new int[size];
        for (int i = 0; i < size; i++) {
            nums[i] = i - size / 2; // 生成从 -size/2 到 size/2 的数
        }

        // 打乱数组顺序
        for (int i = 0; i < size; i++) {
            int j = (int) (Math.random() * size);
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        long startTime = System.currentTimeMillis();
        List<List<Integer>> result = solution.threeSum(nums);
        long endTime = System.currentTimeMillis();

        // 验证结果正确性
        assert validateAllSumsZero(result) : "性能测试：所有三元组的和应该为0";
        assert validateNoDuplicates(result) : "性能测试：不应该有重复三元组";

        System.out.println("  数组大小: " + size + ", 结果数量: " + result.size() +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度为O(n²)，对于合理大小的输入应该很快完成
        assert (endTime - startTime) < 5000 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 辅助方法：最坏情况性能测试
     */
    private static void testWorstCasePerformance(S6_Mid_15_三数之和 solution) {
        // 创建大量重复元素的数组
        int[] nums = new int[300];

        // 前100个是-1，中间100个是0，后100个是1
        for (int i = 0; i < 100; i++) {
            nums[i] = -1;
            nums[i + 100] = 0;
            nums[i + 200] = 1;
        }

        long startTime = System.currentTimeMillis();
        List<List<Integer>> result = solution.threeSum(nums);
        long endTime = System.currentTimeMillis();

        // 验证结果
        assert validateAllSumsZero(result) : "最坏情况：所有三元组的和应该为0";
        assert validateNoDuplicates(result) : "最坏情况：不应该有重复三元组";
        assert result.size() == 1 : "最坏情况：应该只有一个三元组[-1,0,1]";
        assert containsTriplet(result, new int[]{-1, 0, 1}) : "最坏情况：应该包含[-1,0,1]";

        System.out.println("  最坏情况测试 - 数组大小: 300, 结果数量: " + result.size() +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        assert (endTime - startTime) < 1000 : "最坏情况：执行时间过长";
    }
}
